#! /usr/bin/env python

import sys
from optparse import OptionParser
import random

from common.zerror import zassert


# finds the highest nonempty queue
# -1 if they are all empty
def FindQueue(_hiQueue, _queue):
    q = _hiQueue
    while q > 0:
        if len(_queue[q]) > 0:
            return q
        q -= 1
    if len(_queue[0]) > 0:
        return 0
    return -1


class MLFQCore:
    def __init__(self, seed=0, numQueues=3, quantum=10, allotment=1, quantumList='', allotmentList='',
                 numJobs=3, maxlen=100, maxio=10, boost=0, iotime=5, stay=False, iobump=False, jlist='',
                 compute=False):
        self.allotment = None
        self.quantum = None
        parser = OptionParser()
        parser.add_option('-s', '--seed', help='the random seed',
                          default=seed, action='store', type='int', dest='seed')
        parser.add_option('-n', '--numQueues',
                          help='number of queues in MLFQ (if not using -Q)',
                          default=numQueues, action='store', type='int', dest='numQueues')
        parser.add_option('-q', '--quantum', help='length of time slice (if not using -Q)',
                          default=quantum, action='store', type='int', dest='quantum')
        parser.add_option('-a', '--allotment', help='length of allotment (if not using -A)',
                          default=allotment, action='store', type='int', dest='allotment')
        parser.add_option('-Q', '--quantumList',
                          help='length of time slice per queue level, specified as '
                               'x,y,z,... where x is the quantum length for the highest '
                               'priority queue, y the next highest, and so forth',
                          default=quantumList, action='store', type='string', dest='quantumList')
        parser.add_option('-A', '--allotmentList',
                          help='length of time allotment per queue level, specified as '
                               'x,y,z,... where x is the # of time slices for the highest '
                               'priority queue, y the next highest, and so forth',
                          default=allotmentList, action='store', type='string', dest='allotmentList')
        parser.add_option('-j', '--numJobs', default=numJobs, help='number of jobs in the system',
                          action='store', type='int', dest='numJobs')
        parser.add_option('-m', '--maxlen', default=maxlen, help='max run-time of a job ' +
                                                                 '(if randomly generating)',
                          action='store', type='int', dest='maxlen')
        parser.add_option('-M', '--maxio', default=maxio,
                          help='max I/O frequency of a job (if randomly generating)',
                          action='store', type='int', dest='maxio')
        parser.add_option('-B', '--boost', default=boost,
                          help='how often to boost the priority of all jobs back to ' +
                               'high priority', action='store', type='int', dest='boost')
        parser.add_option('-i', '--iotime', default=iotime,
                          help='how long an I/O should last (fixed constant)',
                          action='store', type='int', dest='ioTime')
        parser.add_option('-S', '--stay', default=stay,
                          help='reset and stay at same priority level when issuing I/O',
                          action='store_true', dest='stay')
        parser.add_option('-I', '--iobump', default=iobump,
                          help='if specified, jobs that finished I/O move immediately '
                               'to front of current queue',
                          action='store_true', dest='iobump')
        parser.add_option('-l', '--jlist', default=jlist,
                          help='a comma-separated list of jobs to run, in the form '
                               'x1,y1,z1:x2,y2,z2:... where x is start time, y is run '
                               'time, and z is how often the job issues an I/O request',
                          action='store', type='string', dest='jlist')
        parser.add_option('-c', help='compute answers for me', action='store_true',
                          default=compute, dest='solve')
        (self.options, self.args) = parser.parse_args()
        self.deal_args()

    def show_args(self):
        options = self.options
        print('作业数', options.numJobs)
        print('队列数', options.numQueues)
        for i in range(len(self.quantum) - 1, -1, -1):
            print('队列%2d 的时间分配为%3d' % (i, self.allotment[i]))
            print('队列%2d 的RR时间片为%3d' % (i, self.quantum[i]))
        print('boost', options.boost)
        print('ioTime', options.ioTime)
        print('stayAfterIO', options.stay)
        print('iobump', options.iobump)

    def deal_args(self):
        options = self.options
        random.seed(options.seed)

        # MLFQ: How Many Queues
        numQueues = options.numQueues

        quantum = {}
        if options.quantumList != '':
            # instead, extract number of queues and their time slice
            quantumLengths = options.quantumList.split(',')
            numQueues = len(quantumLengths)
            qc = numQueues - 1
            for i in range(numQueues):
                quantum[qc] = int(quantumLengths[i])
                qc -= 1
        else:
            for i in range(numQueues):
                quantum[i] = int(options.quantum)

        allotment = {}
        if options.allotmentList != '':
            allotmentLengths = options.allotmentList.split(',')
            if numQueues != len(allotmentLengths):
                zassert(False, 'number of allotments specified must match number of quantums')
            qc = numQueues - 1
            for i in range(numQueues):
                allotment[qc] = int(allotmentLengths[i])
                if qc != 0 and allotment[qc] <= 0:
                    zassert(False, 'allotment必须是正数')
                qc -= 1
        else:
            for i in range(numQueues):
                allotment[i] = int(options.allotment)

        self.quantum = quantum
        self.allotment = allotment

        hiQueue = numQueues - 1

        # MLFQ: I/O Model
        # the time for each IO: not great to have a single fixed time but...
        ioTime = int(options.ioTime)

        # This tracks when IOs and other interrupts are complete
        ioDone = {}

        # This stores all info about the jobs
        job = {}

        # seed the random generator
        random.seed(options.seed)

        # jlist 'startTime,runTime,ioFreq:startTime,runTime,ioFreq:...'
        jobCnt = 0
        if options.jlist != '':
            allJobs = options.jlist.split(':')
            for j in allJobs:
                jobInfo = j.split(',')
                if len(jobInfo) != 3:
                    zassert(False, 'Badly formatted job string. Should be x1,y1,z1:x2,y2,z2:...'
                                   'where x is the startTime, y is the runTime, and z is the I/O frequency.')
                assert (len(jobInfo) == 3)
                startTime = int(jobInfo[0])
                runTime = int(jobInfo[1])
                ioFreq = int(jobInfo[2])
                job[jobCnt] = {'currPri': hiQueue, 'ticksLeft': quantum[hiQueue],
                               'allotLeft': allotment[hiQueue], 'startTime': startTime,
                               'runTime': runTime, 'timeLeft': runTime, 'ioFreq': ioFreq, 'doingIO': False,
                               'firstRun': -1}
                if startTime not in ioDone:
                    ioDone[startTime] = []
                ioDone[startTime].append((jobCnt, 'JOB BEGINS'))
                jobCnt += 1
        else:
            # do something random
            for j in range(options.numJobs):
                startTime = 0
                runTime = int(random.random() * (options.maxlen - 1) + 1)
                ioFreq = int(random.random() * (options.maxio - 1) + 1)

                job[jobCnt] = {'currPri': hiQueue, 'ticksLeft': quantum[hiQueue],
                               'allotLeft': allotment[hiQueue], 'startTime': startTime,
                               'runTime': runTime, 'timeLeft': runTime, 'ioFreq': ioFreq, 'doingIO': False,
                               'firstRun': -1}
                if startTime not in ioDone:
                    ioDone[startTime] = []
                ioDone[startTime].append((jobCnt, 'JOB BEGINS'))
                jobCnt += 1

        numJobs = len(job)

        print('作业列表:')
        for i in range(numJobs):
            print('  作业%2d: 开始时间%3d - 运行时间%3d - IO间隔%3d' % (i, job[i]['startTime'],
                                                                          job[i]['runTime'],
                                                                          job[i]['ioFreq']))

        if options.solve is False:
            print('\n对给定的工作负载计算执行序列，为每个任务计算响应时间和周转时间\n'
                  '使用答案模式获得问题的答案')
            return

        # initialize the MLFQ queues
        queue = {}
        for q in range(numQueues):
            queue[q] = []

        # TIME IS CENTRAL
        currTime = 0

        # use these to know when we're finished
        totalJobs = len(job)
        finishedJobs = 0

        print('\n执行序列:\n')

        while finishedJobs < totalJobs:
            # find highest priority job
            # run it until either
            # (a) the job uses up its time quantum
            # (b) the job performs an I/O

            # check for priority boost
            if options.boost > 0 and currTime != 0:
                if currTime % options.boost == 0:
                    print('[ 时间 %d ] BOOST ( 每 %d ms )' % (currTime, options.boost))
                    # remove all jobs from queues (except high queue) and put them in high queue
                    for q in range(numQueues - 1):
                        for j in queue[q]:
                            if job[j]['doingIO'] is False:
                                queue[hiQueue].append(j)
                        queue[q] = []

                    # change priority to high priority
                    # reset number of ticks left for all jobs (just for lower jobs?)
                    # add to highest run queue (if not doing I/O)
                    for j in range(numJobs):
                        # print '-> Boost %d (timeLeft %d)' % (j, job[j]['timeLeft'])
                        if job[j]['timeLeft'] > 0:
                            # print '-> FinalBoost %d (timeLeft %d)' % (j, job[j]['timeLeft'])
                            job[j]['currPri'] = hiQueue
                            job[j]['ticksLeft'] = allotment[hiQueue]
                    # print 'BOOST END: QUEUES look like:', queue

            # check for any I/Os done
            if currTime in ioDone:
                for (j, type) in ioDone[currTime]:
                    q = job[j]['currPri']
                    job[j]['doingIO'] = False
                    print('[ 时间 %d ] %s by 作业%d' % (currTime, type, j))
                    if options.iobump is False or type == 'JOB BEGINS':
                        queue[q].append(j)
                    else:
                        queue[q].insert(0, j)

            # now find the highest priority job
            currQueue = FindQueue(hiQueue, queue)
            if currQueue == -1:
                print('[ 时间 %d ] 停止运行' % currTime)  # IDLE
                currTime += 1
                continue

            # there was at least one runnable job, and hence ...
            currJob = queue[currQueue][0]
            if job[currJob]['currPri'] != currQueue:
                zassert(False, 'currPri[%d] does not match currQueue[%d]' % (job[currJob]['currPri'], currQueue))

            job[currJob]['timeLeft'] -= 1
            job[currJob]['ticksLeft'] -= 1

            if job[currJob]['firstRun'] == -1:
                job[currJob]['firstRun'] = currTime

            runTime = job[currJob]['runTime']
            ioFreq = job[currJob]['ioFreq']
            ticksLeft = job[currJob]['ticksLeft']
            allotLeft = job[currJob]['allotLeft']
            timeLeft = job[currJob]['timeLeft']

            print('[ 时间 %d ] 运行作业%d 优先级:%d [ TICKS %d ALLOT %d TIME %d (of %d) ]' %
                  (currTime, currJob, currQueue, ticksLeft, allotLeft, timeLeft, runTime))

            if timeLeft < 0:
                zassert(False, 'Error: should never have less than 0 time left to run')

            # UPDATE TIME
            currTime += 1

            # CHECK FOR JOB ENDING
            if timeLeft == 0:
                print('[ 时间 %d ] 作业%d 结束运行' % (currTime, currJob))
                finishedJobs += 1
                job[currJob]['endTime'] = currTime
                # print 'BEFORE POP', queue
                done = queue[currQueue].pop(0)
                # print 'AFTER POP', queue
                assert (done == currJob)
                continue

            # CHECK FOR IO
            issuedIO = False
            if ioFreq > 0 and (((runTime - timeLeft) % ioFreq) == 0):
                # time for an IO!
                print('[ 时间 %d ] IO_START by JOB %d' % (currTime, currJob))
                issuedIO = True
                desched = queue[currQueue].pop(0)
                assert (desched == currJob)
                job[currJob]['doingIO'] = True
                # this does the bad rule -- reset your tick counter if you stay at the same level
                if options.stay == True:
                    job[currJob]['ticksLeft'] = quantum[currQueue]
                    job[currJob]['allotLeft'] = allotment[currQueue]
                # add to IO Queue: but which queue?
                futureTime = currTime + ioTime
                if futureTime not in ioDone:
                    ioDone[futureTime] = []
                print('IO操作结束')
                ioDone[futureTime].append((currJob, 'IO_DONE'))

            # CHECK FOR QUANTUM ENDING AT THIS LEVEL (BUT REMEMBER, THERE STILL MAY BE ALLOTMENT LEFT)
            if ticksLeft == 0:
                if not issuedIO:
                    # IO HAS NOT BEEN ISSUED (therefor pop from queue)'
                    desched = queue[currQueue].pop(0)
                assert (desched == currJob)

                job[currJob]['allotLeft'] -= 1

                if job[currJob]['allotLeft'] == 0:
                    # this job is DONE at this level, so move on
                    if currQueue > 0:
                        # in this case, have to change the priority of the job
                        job[currJob]['currPri'] = currQueue - 1
                        job[currJob]['ticksLeft'] = quantum[currQueue - 1]
                        job[currJob]['allotLeft'] = allotment[currQueue - 1]
                        if issuedIO is False:
                            queue[currQueue - 1].append(currJob)
                    else:
                        job[currJob]['ticksLeft'] = quantum[currQueue]
                        job[currJob]['allotLeft'] = allotment[currQueue]
                        if issuedIO is False:
                            queue[currQueue].append(currJob)
                else:
                    # this job has more time at this level, so just push it to end
                    job[currJob]['ticksLeft'] = quantum[currQueue]
                    if issuedIO is False:
                        queue[currQueue].append(currJob)

        # print out statistics
        print('\n最终统计:')
        responseSum = 0
        turnaroundSum = 0
        for i in range(numJobs):
            response = job[i]['firstRun'] - job[i]['startTime']
            turnaround = job[i]['endTime'] - job[i]['startTime']
            print('  作业%2d: startTime %3d - response %3d - turnaround %3d' % (i, job[i]['startTime'],
                                                                                response, turnaround))
            responseSum += response
            turnaroundSum += turnaround

        print('\n  平均%2d: startTime n/a - response %.2f - turnaround %.2f' % (i,
                                                                                float(responseSum) / numJobs,
                                                                                float(turnaroundSum) / numJobs))


def main():
    core = MLFQCore()


if __name__ == "__main__":
    main()
